pub fn dp_rec_mc(amount: u32) -> u32 {
    const COIN_VALUES: [u32; 8] = [1, 2, 5, 10, 20, 30, 50, 100];

    let mut min_coins = vec![u32::MAX; amount as usize + 1];
    min_coins[0] = 0;

    for amount_so_far in 1..=amount as usize {
        for coin in COIN_VALUES {
            // Check if the coin can be used and if using it results in fewer coins
            if coin as usize <= amount_so_far 
                && 1 + min_coins[amount_so_far - coin as usize] < min_coins[amount_so_far] {
                min_coins[amount_so_far] = 1 + min_coins[amount_so_far - coin as usize];
            }
        }
    }
    // Return the minimum number of coins needed for the given amount
    min_coins[amount as usize]
}
